1. Field of the Invention
The present invention relates to a logic circuit optimization apparatus and its method, and more particularly to a logic circuit optimization apparatus and its method for optimizing the delay of a logic circuit having a hierarchical structure.
2. Description of the Related Art
In designing a logic circuit, an optimization apparatus using a computer system is used to optimize the logic circuit in order to improve the performance of the logic circuit to be designed. In connection with a logic circuit having a hierarchical structure, there has been proposed a method for optimizing the delay of a path which extends over the hierarchical sub-circuits of a logic circuit.
Conventional types of such an optimizing technique include the one disclosed in, e.g., Japanese Patent Laid-open Publication (Kokai) No. Heisei 4-51367 "Logic Circuit Synthesizing Device". FIG. 8 shows the configuration of a conventional logic circuit optimizing apparatus disclosed in the above publication. It is seen from FIG. 8 that the logic circuit optimizing apparatus disclosed in the above publication comprises a hierarchical circuit specification input 110 for entering a logic circuit to be optimized having a hierarchical structure, a delay constraints input 120 for entering delay constraint of the pertinent logic circuit, a circuit database 130 for storing the entered logic circuit and delay constraints, a timing analyzer 140 for performing the timing analysis of the logic circuit held in the circuit database 130, an optimization unit 160 for optimizing the delay according to the prescribed delay constraints, a library input 170 for entering a target library of the logic circuit, a library database 180 for holding the entered library information, and an output 190 for outputting the optimized logic circuit.
The above-described optimization apparatus will be described on its operation. First, the hierarchical circuit specification input 110 enters a logic circuit to be optimized to store in the circuit database 130. The delay constraints input 120 enters delay constraints values which contain clock information, arrival times of signals at the input terminals of a hierarchical sub-circuit, and required times for signals at the output terminals of the hierarchical sub-circuit for the whole circuit or each hierarchical sub-circuit to add to the logic circuit stored in the circuit database 130. According to the clock information such as a rise time, a fall time and a cycle time, the arrival time of the signal (output signal) at the output terminal and the required time of the signal (input signal) at the input terminal can be calculated in view of a setup time and hold time of a storage device such as DFF which performs cycle operation on a prescribed clock.
Then, the library input 170 enters library data which contains information to be used for the timing analysis of respective blocks in a target library and stores in the library database 180. And, the timing analyzer 140 performs the timing analysis of the entire circuit. In view of convenience for describing, the maximum delay time only will be described, but the same procedure can be applied for the minimum delay time.
The timing analysis is performed as follows.
With respect to the arrival time determined for an output pin (hereinafter referred to as the starting point of a circuit) of the input terminal of a hierarchical sub-circuit or the storage device, an internal delay time of the block referring to a lower hierarchical sub-circuit or a primitive device block on the path to which a signal included in the circuit and the wiring delay time of wiring between the blocks are added with reference to the library database 180. And, for each output pin, the maximum a delay time from each input pin is determined as the arrival time at the output pin of the block. The propagation processing on the above-described arrival time is repeated until arriving at the input pin (hereinafter referred to as the end point of circuit) of the output terminal or storage device of the hierarchical sub-circuit. Thus, the time of arrival is determined for the output pin of each block.
If a block is mapped into the target library, the internal delay and wiring delay of the pertinent block are obtained according to a value which can be calculated by combining a state of the circuit and the stored value in the library with reference to the library database 180. And, if a block is not mapped, the delay can be predicted in view of the number of logic stages, or the internal delay and wiring delay time of the block can be predicted according to the complexity and fan-out of logic at the time when a combinational circuit is expressed in a logic equation. A method of predicting based on the complexity of logic and the fan-out is described in a literature, e.g., "Delay Prediction for Technology-Independent Logic Equations" (1992, TAU92 Proceeding).
Then, the required time is propagated in the direction opposite from the propagation of the arrival time. With respect to the required time set at the end of circuit, the internal delay time of the primitive device block on the path to which the signal in the circuit reaches or the block referring to the lower hierarchical sub-circuit and the delay wiring time between blocks are deducted, and the time of requirement is determined to the input pin and output pin of the blocks. The above-described propagation processing of the required time is repeated until arriving at the start point of the circuit. The internal delay of the lower hierarchical sub-circuit can be calculated by performing the timing analysis recursively in the same way.
A difference between the required time and the arrival time calculated as described above is called a slack. A partial circuit with a negative value of slack does not satisfy the delay constraint. In such a partial circuit, a column of blocks from the start to end of the circuit is called a critical path. A path having the slack consisting of smallest blocks is called a maximum critical path. The above description has been made on a case of calculating the maximum delay time. To calculate the minimum delay time, the minimum value of the delay time from each input pin for each output pin is determined as the arrival time at the output pin of the block and propagated.
After performing the timing analysis as described above, the optimizing unit 160 changes the circuit to make the delay of the critical path short and stores in the circuit database 130. When the slacks on all paths become a positive value, it means that the constraint is satisfied. The logic circuit undergone the optimization process is outputted from the output 190.
Normally, when a logic circuit, particularly a large scale circuit such as an LSI, is designed, the logic circuit is divided according to particular partial functions into a hierarchy. FIG. 9 shows an example of the logic circuit designed to have a hierarchical sub-circuit. It is seen from FIG. 9 that a top circuit 901 indicates the whole body of a logic circuit to be designed, in which lower reference hierarchical sub-circuits 902, 903 are referred to. A definition hierarchical sub-circuit 904 of the lower reference hierarchical sub-circuit 902 refers to low order reference hierarchical sub-circuits 905, 906. A definition hierarchical sub-circuit 907 of the lower reference hierarchical sub-circuit 905 is a least significant hierarchical sub-circuit and configured of a primitive device block only. And, there is no lower reference hierarchical sub-circuit.
The logic circuit is designed in the form of a hierarchical sub-circuit because a partial circuit can be designed and verifying for each particular function with respect to a large-scale logic circuit, designing efficiency can be improved, another designer can work on each partial circuit in parallel, a designing period can be made short, and a time required for logic synthesis can be made short. In a case of designing a logic circuit by using a logic synthesis system, when it is assumed that the calculation complexity of an optimization algorithm is proportional with the n-th power of the number of elements, it is generally known that n is larger than 1 in various optimization algorithms. In other words, by dividing to partial circuits, the circuit scale to be processed one time is made small and the number of elements is decreased, so that a total processing time can be made short.
Here, it is assumed that there is a combinational circuit having a path which extends over hierarchical sub-circuits as shown in FIG. 10. Lower hierarchical sub-circuits 1002, 1003 are within a higher hierarchical sub-circuit 1001, DFF 1004 and combinational circuits 1005, 1006 are within the lower hierarchical sub-circuit 1002, and DFF 1009 and combinational circuits 1007, 1008 are within the lower hierarchical sub-circuit 1003. The output pin of DFF 1004 becomes the start point of the path, and after getting out of the hierarchical sub-circuit 1002 via the combinational circuits 1005, 1006, enters the hierarchical sub-circuit 1003, and reaches the input pin which is the end point of DFF 1009 via the combinational circuits 1007, 1008.
In order to simplify the model, the setup hold time, clock skew, distinction between rising and falling, maximum delay, minimum delay and wiring delay time of DFF 1004, 1009 are disregarded. It is assumed that the delay times of respective combinational circuits from 1005 to 1008 are 1 ns, 2 ns, 2 ns and 4 ns, respectively. When the arrival time of the output pin of DFF 1004 is 0 ns and the required time of the input pin of DFF1009 is 6 ns, the arrival time at the output pins of the combinational circuits 1005 to 1008 become 1 ns, 3 ns, 5 ns and 9 ns, respectively. All slacks on this path have -3 ns, and the hierarchical sub-circuits 1002, 1003 have the same delay constraint of -3 ns determined with respect to this path. Since the optimization of delay is performed on each hierarchical sub-circuit, when it is assumed that the hierarchical sub-circuit 1004 is optimized first for example, it is regarded that the delay constraint of the path can be satisfied if shortening of 3 ns can be completed by only the hierarchical sub-circuit 1004 because the constraint of minimizing the delay by 3 ns has been determined. In other words, the hierarchical sub-circuit 1002 is not required to be optimized.
As described above, the conventional optimizing technique, which optimizes the delay of a path which extends over hierarchical sub-circuits of a logic circuit, optimizes each hierarchical sub-circuit without considering the possibility of optimizing delay, resulting in optimization with very poor balance depending on the order of selecting hierarchical sub-circuits to be optimized in view of the entire path. Therefore, it has disadvantages that the logic circuit has a large area, and the execution time becomes long because the optimization is repeated.
As to a logic circuit having a hierarchical structure, another optimizing technique for optimizing a delay of a path which extends over hierarchical sub-circuits of a logic circuit is disclosed in, e.g., Japanese Patent Laid-Open Publication (Kokai) No. Heisei 4-320575 "Logic Synthesizing Method and Its Apparatus". The apparatus in this publication has a hierarchy expanding unit for expanding hierarchical type logic circuit information into expansion type logic circuit information, a logic optimizing unit and a hierarchical sub-circuit restoring unit for converting the optimized expansion type logic circuit information into hierarchical type logic circuit information, expands the hierarchical sub-circuit prior to the optimization, optimizes the delay of each critical path, and restores to the original hierarchical structure after completing the optimization. Thus, the critical path can be optimized in good balance with good efficiency without a large area overhead.
However, since the expansion of the hierarchical structure of a logic circuit makes the circuit to be optimized large in size, it takes a long time to complete the optimization. And, it may sometimes happen as a result of optimization that the blocks in the boundary of hierarchical sub-circuits disappear and the terminal of the original hierarchical sub-circuit cannot be restored.